/*
 * @lc app=leetcode id=64 lang=cpp
 *
 * [64] Minimum Path Sum
 */
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {

        int row = grid.size();
        if (row < 1) {
            return 0;
        }

        int col = grid[0].size();
        vector<vector<int>> memo(row, vector<int>(col, 0));
        memo[0][0] = grid[0][0];
        for (int i=1; i<col; i++) {
            memo[0][i] = memo[0][i-1] + grid[0][i];
        }
        for (int i=1; i<row; i++) {
            memo[i][0] = memo[i-1][0] + grid[i][0];
        }

        for (int i=1; i<row; i++) {
            for (int j=1; j<col; j++) {
                memo[i][j] = min(memo[i-1][j],memo[i][j-1]) + grid[i][j];
            }
        }
        return memo[row-1][col-1];
    }
};

